package com.jack.leetcode.eachproblem_2020;

/**
 * 非负整数组
 * Created by zhang_j on 2020/11/13
 */
public class 目标和 {

    public static int findTargetSumWays(int[] nums, int S) {
        if(nums == null){
            return 0;
        }
        int n = nums.length;
        int sum = 0;
        for(int i : nums){
            sum += Math.abs(i);
        }
        if(Math.abs(S) > Math.abs(sum)){
            return 0;
        }
        int t = sum * 2 + 1;
        int[][] dp = new int[n][t];
        if(nums[0] == 0){
            dp[0][sum] = 2;
        }else{
            dp[0][sum - nums[0]] = 1;
            dp[0][sum + nums[0]] = 1;
        }
        for(int i = 1;i < n;i++){
            for(int j = 0;j < t;j++){
                int l = j - nums[i] >= 0 ? j - nums[i] : 0;
                int r = j + nums[i] < t ? j + nums[i] : 0;
                dp[i][j] = dp[i - 1][l] + dp[i - 1][r];
            }
        }
        return dp[n - 1][S + sum];
    }

    public static void main(String[] args) {
        int[] a = {2,2,3,-4};
        System.out.println(findTargetSumWays(a, 3));
        int[] b = {0,0,0,1};
        System.out.println(findTargetSumWays(b, 1));
    }
}
